import math

li = [54, 26, 93, 17, 77, 31, 44, 55, 20]


def merge(li):
    result = []
    l_li = li[0:len(li) // 2]
    r_li = li[len(li) // 2:]
    while len(l_li) != 0 and len(r_li) != 0:
        if l_li[0] <= r_li[0]:
            result.append(l_li.pop(0))
        else:
            result.append(r_li.pop(0))
    if len(l_li) == 0:
        result.extend(r_li)
    else:
        result.extend(l_li)
    return result


def merge_sort(li):
    new_li = []
    step = 2
    while step < len(li):
        num = math.ceil(len(li) / step)
        for i in range(num):
            l_i = i * step
            r_i = (i + 1) * step
            new_li.extend(merge(li[l_i:r_i]))
        li = new_li
        new_li = []
        step *= 2
    merge(li)
    return li


print(merge_sort(li))
